a. Technical Field or Field of the Invention
The present invention relates to an optical system capable of creating a potential field map of a bounded two dimensional region containing a goal location and arbitrary number of obstacles. The potential field map of the region can be used by an autonomous mobile robot to guide itself from any initial location to a goal location while avoiding obstacles which may be present in the robot's workspace.
b. Description of the Prior Art
There are many types of robot systems which include such devices as wheeled vehicles, manipulator arms, multi-fingered hands, and free flying platforms. The robot workspace may be partially filled with obstacles, and regions which it cannot traverse due to physical or other constraints. For a robot to move without running into the obstacles, it is necessary to determine a robot path from an initial location to a designated goal location within the bounded two dimension workspace. FIG. 1(a) shows a plan view of such a workspace. This plan view could represent a room bounded by walls and containing furniture of various shapes, or a region of outdoor terrain with the obstacles representing trees, buildings, or areas of ground which are too steep for the robot to traverse. However, the workspace is not limited to these two examples.
Many types of path planning systems have been investigated, see Chapter 7, "Potential Field Methods," of Jean-Claude Latombe's Robot Motion Planning, Kluwer Academic Publishers, Massachusetts (1991). Generally, there are two basic types of robot path planning systems: (1) those methods which attempt to find an optimal path, for instance, a minimal distance path; and (2) those which attempt to find an efficient path.
In the potential field method, the robot is treated as a charged object, the goal is an oppositely charged region, and obstacles are regions having the same polarity charge as the robot. Each location in the robot workspace is treated as having a potential energy U(x). In practice, the workspace is usually divided into some finite number of cells. Each cell is assigned a potential value and the robot moves from cell to cell. The robot, because it is treated as being charged, follows the potential gradient responding to a force F(x)=- U(x). The conventional potential field methods, therefore, require that a potential value be calculated for each cell. Generally, the field throughout the workspace due to each obstacle and the goal are calculated separately and then added to produce a potential field map for the entire workspace.
A significant problem with the conventional potential field approach is that it often produces local potential minima. Because the robot path follows the potential gradient, local minima in the potential field map can cause the robot path to include traps which prevent the robot from reaching a goal 6. FIG. 1(b) schematically illustrates this problem for a workspace containing a single simple obstacle 2. At a point directly behind the obstacle 2 from the goal 6, the force on the robot 4 is either directly away from or towards the obstacle, or the robot 4 may reach a local minimum where the forces exactly cancel.
Another problem arises in conventional methods which contribute positive potential fields. FIG. 1(c) shows three levels of equipotential lines, with values P.sub.3 &gt;P.sub.2 &gt;P.sub.1, for a robot workspace containing two obstacles 2. Those edges of the obstacles 2 which are close together form a high potential ridge (at potential value P.sub.3). This high potential ridge forms a local minimum at potential P.sub.2. This kind of local minima can be eliminated by using a spatially extending potential only for the goal 6. With this approach, the obstacles are still located at maximum potential locations, but they have no field which extends beyond their boundaries. This solution causes its own problems with local minima, as shown in FIG. 1(d). As the potential monotonically decreases the closer the robot gets to the goal 6, the robot will proceed straight for the goal until it hits an obstacle. The robot then slides along the obstacles until it either slides around the obstacle's edge or is trapped at a local minimum.
One method that avoids all the local minima situations shown in FIGS. 1(b)-1(d) is schematically illustrated in FIGS. 2(a)-2(d). A simple one obstacle robot workspace is shown in FIG. 2(a). The obstacles are considered maximum potential regions which do not exert forces beyond their boundaries. The goal location is the source of an expanding low potential region which starts in a small area and grows uniformly until it reaches an obstacle. Upon reaching an obstacle, the goal's "field" spreads around the obstacle. The field stops expanding when it has filled the entire workspace. In FIG. 2(b) the first two equipotential lines surrounding the goal 6 are shown. When the equipotential lines reach obstacle 2, the obstacle's charge distorts the equipotential lines as shown in FIG. 2(c). The completed pattern in FIG. 2(d) contains no local minima. A robot 4 located behind the obstacle 2 is guided around it, following a path 3 such as that shown in FIG. 2(d). In a conventional digital electronic implementation, this system runs in O(N.sup.3/2) time, where N is the number of cells. Alternative techniques for overcoming local minima are even more computationally intensive. Therefore, digital implementation of this mapping system has proven laborious, particularly in a robot workspace where the obstacles are moving.